#include <vector>

using namespace std;

// 斐波那契数
// 斐波那契数 （通常用 F(n) 表示）形成的序列称为 斐波那契数列
// 该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。
// 也就是：F(0) = 0，F(1) = 1
// F(n) = F(n - 1) + F(n - 2)，其中 n > 1
// 给定 n ，请计算 F(n)
// 测试链接 : https://leetcode.cn/problems/fibonacci-number/
// 注意：最优解来自矩阵快速幂，时间复杂度可以做到O(log n)
// 后续课程一定会讲述！本节课不涉及！

// 相关的加餐链接：
// 70. 爬楼梯：https://leetcode.cn/problems/climbing-stairs/
// 1137. 第 N 个泰波那契数：https://leetcode.cn/problems/n-th-tribonacci-number/
// 50. Pow(x, n)：https://leetcode.cn/problems/powx-n/，这道题的答案，我会帖到本文件末尾

class Solution 
{
public:
    // 暴力递归，时间复杂度 O(2^N)，空间复杂度 O(N)
    int f1(int i)
    {
        if(i == 0) return 0;
        if(i == 1) return 1;
        return f1(i - 1) + f1(i - 2);
    }

    int fib1(int n) 
    {
        return f1(n);
    }

    // 暴力尝试改记忆化搜索
	// 从顶到底的动态规划
    // 时间复杂度 O(N)，空间复杂度 O(N)
    int f2(int i, vector<int>& dp)
    {
        if(i == 0) return 0;
        if(i == 1) return 1;
        if(dp[i] != -1) return dp[i];

        int ans = f2(i - 1, dp) + f2(i - 2, dp);
        dp[i] = ans;
        return ans;
    }

    int fib2(int n) 
    {
        vector<int> dp(n + 1, -1);
        return f2(n, dp);
    }

    // 严格位置依赖的动态规划
	// 从底到顶的动态规划
    // 时间复杂度 O(N)，空间复杂度 O(N)
    int fib3(int n)
    {
        if(n <= 1) return n;
        vector<int> dp(n + 1);
        dp[1] = 1;
        for(int i = 2; i <= n; ++i) dp[i] = dp[i - 1] + dp[i - 2];
        return dp[n];
    }

    // 空间压缩的动态规划，空间复杂度 O(1)
    int fib4(int n)
    {
        if(n <= 1) return n;
        int lastLast = 0, last = 1;
        for(int i = 2, cur; i <= n; ++i)
        {
            cur = lastLast + last;
            lastLast = last;
            last = cur;
        }
        return last;
    }
    
    // 矩阵快速幂
    // 矩阵快速幂用于用来解决，类似于 f(i) = a * f(i - 1) + 
    // b * f(i - 2) + c * f(i - 3) + ... 的 dp 问题，也就是
    // 使用矩阵快速幂来优化线性 dp
    // 我们知道，斐波那契数列的动态转移方程是 dp[i] = dp[i - 1] + dp[i - 2]
    // 而 dp[i - 1] = 1 * dp[i - 1] + 0 * dp[i - 2]（这个是一个恒等式）
    // 我们将上面的两个式子写成矩阵的形式，如下
    // | dp[i]     |   =    | 1  1 | * | dp[i - 1] | （矩阵乘法，行乘列）
    // | dp[i - 1] |        | 1  0 |   | dp[i - 2] |
    //  记其为 f(i)           矩阵q    则其为 f(i - 1)
    // 那么就有了 f(i) = q * f(i - 1)，则 f(i) = q^(i - 1) * f(1)
    // 那么我们现在就要求矩阵 q 的 i - 1 次方是多少，也就相当于求 q 的 n 
    // 次方。只要求出它，就能够求出 f(i)，也就求出 dp[i] 了
    // 记 q^(i - 1) = | a b |   f(1) = | dp[1] |  f(i) = | dp[i]     |
    //                | c d |          | dp[0] |         | dp[i - 1] |
    // 则 dp[i] = a * dp[1] + b * dp[0] = a，记 ret = q^(i - 1)，则
    // dp[i] = ret[0][0]

    // 矩阵相乘 a 和 b 都是 2 * 2 的矩阵
    vector<vector<int>> matrix_multiply(vector<vector<int>>& a, vector<vector<int>>& b)
    {
        vector<vector<int>> c{{0, 0}, {0, 0}}; // 用来保存结果
        for(int i = 0; i < 2; ++i)
        {
            for(int j = 0; j < 2; ++j)
            {
                c[i][j] = a[i][0] * b[0][j] + a[i][1] * b[1][j]; // 矩阵相乘，行乘列
            }
        }
        return c;
    }

    // 这里是快速幂，求矩阵 a 的 n 次方
    // 这里求 a 的 n 次方，和 50. Pow(x, n) 这道题是一样的，可以做一下这道题
    // 假设 n 等于 10，则 n 的二进制表示为 1010
    // 那么 a^n = a^(2^1 + 2^3)，注：2^1 + 2^3 = 2 + 8 = 10
    // 那么现在相等于求 a^2 * a^8，那么而 a^2 = a * a，这其实是和
    // n 右移后最低位为 1 是对应起来的，同理 a^8 是和 n 右移三次后
    // 最低位为 1 对应起来的，相当于只要 n 的最低位为 1 时，都要将此时
    // 的 a 与 ret 相乘（需要注意的是，只要 n 右移一次，a 都要乘等一次 a）
    vector<vector<int>> matrix_pow(vector<vector<int>>& a, int n)
    {
        vector<vector<int>> ret{{1, 0}, {0, 1}}; // 单位矩阵
        while(n)
        {
            if(n & 1)
            {
                ret = matrix_multiply(ret, a);
            }
            n >>= 1;
            a = matrix_multiply(a, a);
        }
        return ret;
    }
    
    // 时间复杂度 O(logN)
    int fib5(int n)
    {
        if(n <= 1) return n;

        vector<vector<int>> a{{1, 1}, {1, 0}}; // 系数矩阵
        vector<vector<int>>&& ret = matrix_pow(a, n - 1);
        return ret[0][0];
    }
};

// 50. Pow(x, n)：https://leetcode.cn/problems/powx-n/
// 快速幂 + 迭代，时间复杂度 O(logN)
class Solution
{
private:
    double quickMul1(double x, long n)
    {
        double ret = 1.0;
        while (n > 0)
        {
            if (n & 1)
            {
                ret *= x; // 最低位为 1，ret 就要乘上 x
            }
            // n 每往右移动一位，x 都要乘上 x 一次
            n >>= 1;
            x *= x; 
        }
        return ret;
    }

public:
    double myPow(double x, int n)
    {
        long N = n;
        return N >= 0 ? quickMul1(x, N) : 1.0 / quickMul1(x, -N);
    }
};

// master公式
//   a. 所有子问题规模相同的递归才能用master公式，T(n) = a * T(n/b) + O(n^c)，a、b、c都是常数
//   b. 如果log(b,a) < c，复杂度为：O(n^c)
//   c. 如果log(b,a) > c，复杂度为：O(n^log(b,a))
//   d. 如果log(b,a) == c，复杂度为：O(n^c * logn)
// 一个补充
//     T(n) = 2*T(n/2) + O(n*logn)，时间复杂度是O(n * ((logn)的平方))，证明过程比较复杂，记住即可
// a = 1  b = 2  c = 0，log(b,a) == c ==> 复杂度为 O(N^0 * logN) = O(logN)
// 50. Pow(x, n)：https://leetcode.cn/problems/powx-n/
// 快速幂 + 递归，时间复杂度 O(logN)
class Solution 
{
private:
    double pow(double x, long n)
    {
        if(n == 0) return 1.0;
        
        double tmp = pow(x, n / 2);
        return n % 2 == 0 ? tmp * tmp : tmp * tmp * x;
    }
public:
    double myPow(double x, int n) 
    {
        return n < 0 ? 1.0 / pow(x, -(long)n) : pow(x, n);
    }
};